The present invention relates to computer modeling of geometric shapes and, in particular, to the modeling object surfaces using simple soft creases for subdivision surfaces.
In the world of 3 dimensional computer graphics, simple elements such as boxes and spheres are used to construct complex figures. For example, an arm may be initially depicted by joining a couple of boxes together. A mesh is applied to this initial representation of an arm. The mesh subdivides the initial representation of the arm with intersecting lines. Then subdivision algorithms are used to refine the mesh to get a smoother appearing arm.
Subdivision is an algorithmic technique that is used to generate smooth surfaces as a sequence of successively refined polyhedral meshes. Its origin dates back to 1978 when Catmull and Clark first proposed to generalize spline-patch methods to meshes of arbitrary topology. The algorithms they developed are often referred to as Catmull-Clark subdivision rules. These rules are exceptionally simple and work for arbitrary control meshes to produce smooth surfaces. Subdivision-based representations of complex geometry can be manipulated and rendered very efficiently, which makes subdivision a highly suitable tool for interactive animation and modeling systems.
The Catmull-Clark subdivision rules can be expressed as xe2x80x9cvertex masksxe2x80x9d by which the vertices at a one level (M+1) are constructed from vertices at the previous level (M). The following are the formulas for Catmull-Clark:
Standard Catmull-Clark
In normal Catmull-Clark, the subdivision masks are as follows:
A new level M+1 vertex is created in the center of each face, where the position of the new vertex is determined by the formula:
P(F)=Sum(F.vj)/Fdegxe2x80x83xe2x80x831.
where P(F) is the position of the new vertex in the center of face F;
Sum(F.vj) is the sum of the positions of all vertices that define the face F; and
F deg is the degree of face F.
A new level M+1 vertex is also created in the center of each edge. The position of each new mid-edge vertex is determined by the formula:
P(E)=(E.v0+E.v1+P(E.f0)+P(E.f1))/4xe2x80x83xe2x80x832(a).
where P(E) is the position of the new vertex in the middle of edge E;
E.v0 and E.v1 are the positions of the two endpoints of edge E;
and P(E.f0) and P(E.f1) are the positions of the face centers (as created by equation 1) for each of the two faces which use edge E.
Finally, the position of each level-M vertex is modified by the position of its neighbors to obtain the level M+1 version of the same vertex. For a vertex with valence n (e.g., n faces and n edges), this formula is given by
P(V)=((nxe2x88x922)/n)*V+Sum(V.Ej.ov)/n2+Sum(P(V.Fj))/n2xe2x80x83xe2x80x833(a).
where P(V) is the new position of vertex V;
V.Ej.ov represents the vertex at the other end of edge V.Ej from V (for each edge which uses vertex V);
and P(V.Fj) represents the position of the face center (as created by equation 1) for each of the faces which use vertex V.
Equation 3(a) is referred to herein as the xe2x80x9czero crease vertex rulexe2x80x9d.
The above completely describes the position of the vertices for the next level. To describe the faces and edges for the next level, we merely note that every face at level M is divided up into a bunch of 4-sided faces at level M+1, as follows: a new face is created in every xe2x80x9ccornerxe2x80x9d of the level-M face using a face point, an edge point, a vertex point, and another edge point. This is illustrated in FIG. 5 and FIG. 6. FIG. 5 shows one face of a level-M mesh. FIG. 6 shows a level M+1 mesh where the one face of the level-M mesh is divided into 4 faces. Each face at level M+1 uses one of the original vertices, plus the edge midpoint on each side, and the face center point. Level M+1 edges are just those resulting from this arrangement of facesxe2x80x94there are new edges connecting edge points with face points as well as dividing the level M edges in two, thus connecting edge points to vertex points.
The subdivided mesh that results from several iterations of Catmull-Clark formulas is very smooth. For example, FIG. 1 illustrates a cube, and FIG. 2 depicts a smooth, spherical shape produced by iteratively applying the Catmull-Clark formulas to all surfaces of the cube in FIG. 1. Unfortunately, smooth surfaces are insufficient in addressing all of the needs of computer graphics. For example, a finger is rounded everywhere except the fingernail. Creases are used to delineate the fingernail. A well established xe2x80x9chard creasexe2x80x9d variation on the subdivision rules allows the subdivision result to retain such creases.
Hard Creases
A hard crease may be applied to edges in the original (level-0) mesh to create a discontinuity in the smoothness of a surface. For example, FIG. 3 depicts a shape produced by assigning hard creases to each of the four edges on the top of a box, and then applying the modified subdivision rules as described below.
The path that defines the edges associated with a hard crease is a border between where the smoothness of the various surfaces affect each other. The flat surface top of the shape in FIG. 3 is achieved because the surface top only depends on the four points on the top of the box. The four points at the top of the box do not influence the rest of the points of the box because the hard crease defines the limit of what affects the top surface.
A widely accepted standard for xe2x80x9chard creasesxe2x80x9d holds that the edges forming the crease should behave like a cubic spline, ignoring the contributions of geometry on either side. The following formulas are standard modifications made to the Catmull-Clark formulas to achieve hard creases:
The formula for determining the position of the vertex at the center of a face is unchanged.
Edge vertices for hard-crease edges discard the face contributions and become simple midpoints:
P(E)=(E.v0+E.v1)/2xe2x80x83xe2x80x832(b).
For vertices with 2 hard-creased edges on edges V.Ec1 and V.Ec2, contributions are included only from those vertices and their neighbors along the crease:
P(V)=3 *V/4+(V.Ec1.ov+V.Ec2.ov)/8xe2x80x83xe2x80x833(b).
where V.Ec1.ov and edges.
Equation 3(b) is referred to herein as the xe2x80x9cunmodified 2-crease vertex rulexe2x80x9d.
Vertices with only 1 creased edge have traditionally been treated the same as non-creased vertices, as in 3(a).
Vertices with three or more creased edges have been fixed in place, i.e.
P(V)=V.xe2x80x83xe2x80x833(c).
where vertices with three or more creased edges are herein referred to as xe2x80x9ccornersxe2x80x9d, and equation 3(c) is referred to herein as the xe2x80x9ccorner rulexe2x80x9d.
The method for creating faces and edges for each subdivision level is identical to the method used in the uncreased version above.
These rules are further disclosed in co-pending application Ser. No. 09/296,046, filed Apr. 21, 1999, by Thomas Burke entitled RELATIONAL MODELING OF TRIMMED NURBS SURFACES, the contents of which is hereby incorporated by reference its entirety.
Although there are methods for creating vertices, modifying those vertices, and creating hard creases, there remains a need for modifying hard creases to achieve an interpolation between hard creases and smooth surfaces. Furthermore there is a need for a simple user interface to execute this interpolation.
Techniques are provided for creating soft creases for subdivision surfaces. Specifically, techniques are provided for creating an interpolation between a hard crease and a smooth surface at every iteration of subdivision, and providing a mechanism for users to determine the degree to which such an interpolation resembles a hard crease or a smooth surface. Techniques are also provided to more consistently handle vertices with some number of creased edges other than 0 or 2 by interpolating between the unmodified Catmull-Clark vertex rule, the 2-crease vertex rule, and the corner rule, which has 3 or more creases.
According to one embodiment of the invention, the following steps are performed when an object is rendered: receiving, in response to user input, a selected value per edge in the original mesh that falls within a range bounded by a first value and a second value; and rendering the object with a soft crease that has an appearance based on the selected value. The soft crease represents an interpolation between a hard crease and a smooth surface. The closer the selected value is to the first value, the more the appearance of the soft crease resembles the hard crease and, conversely, the closer the selected value is to the second value, the more the appearance of the soft crease resembles the smooth surface.